/****************************************************************************\
*                                                                            *
*  Copyright 2008 The CAnt2 Project (http://code.google.com/p/cant2)         *
*                                                                            *
*  Licensed under the Apache License, Version 2.0 (the "License");           *
*  you may not use this file except in compliance with the License.          *
*  You may obtain a copy of the License at                                   *
*                                                                            *
*      http://www.apache.org/licenses/LICENSE-2.0                            *
*                                                                            *
*  Unless required by applicable law or agreed to in writing, software       *
*  distributed under the License is distributed on an "AS IS" BASIS,         *
*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  *
*  See the License for the specific language governing permissions and       *
*  limitations under the License.                                            *
*                                                                            *
\****************************************************************************/

#include "StringPool.h"
#include "HashTable.h"

#include <numeric>

/****************************************************************************/

namespace StringPool {
namespace Details {

    typedef HashTable<unsigned> HashToPoolIndex;
    typedef std::vector<std::wstring>   StringPool;

    HashToPoolIndex hashToPoolIndex;
    StringPool      stringPool;

    typedef unsigned fast_uint32_t;

    fast_uint32_t rotl ( fast_uint32_t x, fast_uint32_t cnt )
    {
        return ( x << cnt ) | ( x >> ( 32 - cnt ) );
    }

    void mix ( fast_uint32_t& a, fast_uint32_t& b, fast_uint32_t& c )
    {
        a -= c;  a ^= rotl (c,  4 );  c += b;
        b -= a;  b ^= rotl (a,  6 );  a += c;
        c -= b;  c ^= rotl (b,  8 );  b += a;
        a -= c;  a ^= rotl (c, 16 );  c += b;
        b -= a;  b ^= rotl (a, 19 );  a += c;
        c -= b;  c ^= rotl (b,  4 );  b += a;
    }

    void final ( fast_uint32_t& a, fast_uint32_t& b, fast_uint32_t& c )
    {
        c ^= b; c -= rotl ( b, 14 );
        a ^= c; a -= rotl ( c, 11 );
        b ^= a; b -= rotl ( a, 25 );
        c ^= b; c -= rotl ( b, 16 );
        a ^= c; a -= rotl ( c,  4 );
        b ^= a; b -= rotl ( a, 14 );
        c ^= b; c -= rotl ( b, 24 );
    }

    // ComputeHash implements Bob Jenkins "Lookup3" hashing algorithm.
    // http://burtleburtle.net/bob/hash/doobs.html
    unsigned ComputeHash ( const wchar_t* k, size_t length )
    {
        fast_uint32_t a,b,c;
        a = b = c = 0xdeadbeef + fast_uint32_t ( length << 2 );

        while ( length > 6 )
        {
            a += ( fast_uint32_t ( k[0] ) << 0 ) | ( fast_uint32_t ( k[1] ) << 16 );
            b += ( fast_uint32_t ( k[2] ) << 0 ) | ( fast_uint32_t ( k[3] ) << 16 );
            c += ( fast_uint32_t ( k[4] ) << 0 ) | ( fast_uint32_t ( k[5] ) << 16 );
            mix(a,b,c);
            length -= 3;
            k += 3;
        }

        switch ( length )
        {
            case 6:
                c += ( fast_uint32_t ( k[4] ) << 0 ) | ( fast_uint32_t ( k[5] ) << 16 );
                b += ( fast_uint32_t ( k[2] ) << 0 ) | ( fast_uint32_t ( k[3] ) << 16 );
                a += ( fast_uint32_t ( k[0] ) << 0 ) | ( fast_uint32_t ( k[1] ) << 16 );
                break;
            case 5:
                c += ( fast_uint32_t ( k[4] ) << 0 );
                b += ( fast_uint32_t ( k[2] ) << 0 ) | ( fast_uint32_t ( k[3] ) << 16 );
                a += ( fast_uint32_t ( k[0] ) << 0 ) | ( fast_uint32_t ( k[1] ) << 16 );
                break;
            case 4:
                b += ( fast_uint32_t ( k[2] ) << 0 ) | ( fast_uint32_t ( k[3] ) << 16 );
                a += ( fast_uint32_t ( k[0] ) << 0 ) | ( fast_uint32_t ( k[1] ) << 16 );
                break;
            case 3:
                b += ( fast_uint32_t ( k[2] ) << 0 );
                a += ( fast_uint32_t ( k[0] ) << 0 ) | ( fast_uint32_t ( k[1] ) << 16 );
                break;
            case 2:
                a += ( fast_uint32_t ( k[0] ) << 0 ) | ( fast_uint32_t ( k[1] ) << 16 );
                break;
            case 1:
                a += ( fast_uint32_t ( k[0] ) << 0 );
                break;
            case 0:
                return c; // Only gets here for zero length strings
        }

        final ( a, b, c );

        return c;
    }
}
}

/****************************************************************************/

namespace StringPool {

    Handle Insert ( const std::wstring& string )
    {
        unsigned i;
        unsigned h = Details::ComputeHash ( string.c_str(), string.length() );
        unsigned p = Details::hashToPoolIndex.FindFirstMatching ( h );
        while ( p != Details::HashToPoolIndex::Invalid )
        {
            i = Details::hashToPoolIndex.Get(p);
            if ( Details::stringPool.at(i) == string )
            {
                break;
            }
            p = Details::hashToPoolIndex.FindNextMatching ( p, h );
        }

        if ( p == Details::HashToPoolIndex::Invalid )
        {
            i = unsigned ( Details::stringPool.size() );
            Details::stringPool.push_back ( string );
            Details::hashToPoolIndex.Insert ( h, i );
        }

        return Handle ( i );
    }

    const std::wstring& Lookup ( Handle h )
    {
        return Details::stringPool.at( h.Get() );
    }

}

